#include <string.h>
#include "MemPool.h"
#include "hashtable.h"
#include "slave.h"
#define HASH_MULT_VALUE 11400714819323198485
#define slave_newEntry() slave_acemesh_myalloc_aligned_16(sizeof(struct entry),_MYID)//libc_uncached_aligned_malloc(sizeof(struct entry))
#define slave_newEntryList(length) slave_acemesh_myalloc_aligned_16(length*sizeof(struct entry),_MYID)//libc_uncached_aligned_malloc(length * sizeof(struct entry))

#define slave_newHashMap() slave_acemesh_myalloc_aligned_16(sizeof(struct hashMap),_MYID)
#define slave_newHashMapIterator() slave_acemesh_myalloc_aligned_16(sizeof(struct hashMapIterator),_MYID)
int hashCode(HashMap hashMap, void *key)
{
 /*
     char *k = (char)key;
     unsigned long h = 0;
     while (*k) {
         h = (h << 4) + *k++;
         unsigned long g = h & 0xF0000000L;
         if (g) {
             h ^= g >> 24;
         }
         h &= ~g;
     }
     return h % hashMap->listSize;
*/   
    unsigned long hash = (unsigned long)key * HASH_MULT_VALUE;  // overflow of integer
                                                                // multiplication
    int id = (hash >> 60) & 0xf;//(hashMap->listSize-1);            //
    return id;
}
bool hashEqual(void *key1, void *key2) { 
//printf("dizhi:%p,%p\n",key1,key2);
return strcmp((char *)key1, (char *)key2) ? false : true; 
}
void resetHashMap(HashMap hashMap, int listSize)
{
    if (listSize < 16) return;

    // 键值对临时存储空间
    Entry tempList = slave_newEntryList(hashMap->size);

    HashMapIterator iterator = slave_createHashMapIterator(hashMap);
    int length = hashMap->size;
    for (int index = 0; hasNextHashMapIterator(iterator); index++) {
        // 迭代取出所有键值对
        iterator = nextHashMapIterator(iterator);
        tempList[index].key = iterator->entry->key;
        tempList[index].value = iterator->entry->value;
        tempList[index].next = NULL;
    }
    freeHashMapIterator(&iterator);

    // 清除原有键值对数据
    hashMap->size = 0;
    for (int i = 0; i < hashMap->listSize; i++) {
        Entry current = &hashMap->list[i];
        current->key = NULL;
        current->value = NULL;
        if (current->next != NULL) {
            while (current->next != NULL) {
                Entry temp = current->next->next;
                free(current->next);
                current->next = temp;
            }
        }
    }

    // 更改内存大小
    hashMap->listSize = listSize;
    Entry relist = (Entry)realloc(hashMap->list, hashMap->listSize * sizeof(struct entry));
    if (relist != NULL) {
        hashMap->list = relist;
        relist = NULL;
    }

    // 初始化数据
    for (int i = 0; i < hashMap->listSize; i++) {
        hashMap->list[i].key = NULL;
        hashMap->list[i].value = NULL;
        hashMap->list[i].next = NULL;
    }

    // 将所有键值对重新写入内存
    for (int i = 0; i < length; i++) {
        hashPut(hashMap, tempList[i].key, tempList[i].value);
    }
    free(tempList);
}

void hashPut(HashMap hashMap, void *key, void *value)
{
//printf("hashput:key:%p,value:%p\n",key,value); 
  // if (hashMap->size >= hashMap->listSize) {
//printf("resethashmap\n");      
  // 内存扩充至原来的两倍
        // *注: 扩充时考虑的是当前存储元素数量与存储空间的大小关系，而不是存储空间是否已经存满，
        // 例如:
        // 存储空间为10，存入了10个键值对，但是全部冲突了，所以存储空间空着9个，其余的全部挂在一个上面，
        // 这样检索的时候和遍历查询没有什么区别了，可以简单这样理解，当我存入第11个键值对的时候一定会发生冲突，
        // 这是由哈希函数本身的特性(取模)决定的，冲突就会导致检索变慢，所以这时候扩充存储空间，对原有键值对进行
        // 再次散列，会把冲突的数据再次分散开，加快索引定位速度。
  //      resetHashMap(hashMap, hashMap->listSize * 2);
  //  }

    int index = hashCode(hashMap, key);
    if (hashMap->list[index].key == NULL) {
        hashMap->size++;
        // 该地址为空时直接存储
        hashMap->list[index].key = key;
        hashMap->list[index].value = value;
        //hashMap->list[index].next=NULL;
//printf("@@@@@hashput:list:%p,key:%p,value:%p,next:%p\n",hashMap->list[index],hashMap->list[index].key,hashMap->list[index].value,hashMap->list[index].next);   
 } else {
        Entry current = &hashMap->list[index];
        while (current!=NULL&&current->key != NULL) {
            if (hashEqual(key, current->key)) {
                // 对于键值已经存在的直接覆盖
                current->value = value;
                return;
            }
            current = current->next;
        }

        // 发生冲突则创建节点挂到相应位置的next上
        Entry entry = slave_newEntry();
        entry->key = key;
        entry->value = value;
        entry->next = hashMap->list[index].next;
        //printf("put:entry:%p,entry->next:%p\n",entry,entry->next);
hashMap->list[index].next = entry;
        hashMap->size++;
    }
}

void *hashGet(HashMap hashMap, void *key)
{

//printf("hashget:key:%p\n",key);    
int index = hashCode(hashMap, key);
    Entry entry = &hashMap->list[index];
    if (entry->key == NULL) {
        return NULL;
    }
    while (entry->key != NULL && !hashEqual(entry->key, key) && entry->next != NULL) {
        entry = entry->next;
    }
    if (hashEqual(entry->key, key))
        return entry->value;
    else
        return NULL;
}

bool hashRemove(HashMap hashMap, void *key)
{
   //printf("hashremove\n");
    int index = hashCode(hashMap, key);
    Entry entry = &hashMap->list[index];
    if (entry->key == NULL) {
        return false;
    }
    bool result = false;
    if (hashEqual(entry->key, key)) {
        hashMap->size--;
        if (entry->next != NULL) {
            Entry temp = entry->next;
            entry->key = temp->key;
            entry->value = temp->value;
            entry->next = temp->next;
            free(temp);
        } else {
            entry->key = entry->value = NULL;
        }
        result = true;
    } else {
        Entry p = entry;
        entry = entry->next;
        while (entry != NULL) {
            if (hashEqual(entry->key, key)) {
                hashMap->size--;
                p->next = entry->next;
                free(entry);
                result = true;
                break;
            }
            p = entry;
            entry = entry->next;
        }
    }

    // 如果空间占用不足一半，则释放多余内存
    if (result && hashMap->size < hashMap->listSize / 2) {
        resetHashMap(hashMap, hashMap->listSize / 2);
    }
    return result;
}

bool hashExists(HashMap hashMap, void *key)
{
    //printf("hashexists:%p\n",key);
int index = hashCode(hashMap, key);
    Entry entry = &hashMap->list[index];
//printf("hashMap:%p,entry:%p,key:%p,index:%d\n",&hashMap->list[index],entry,key,index);
    if (entry->key == NULL) {
        return false;
    }
//printf("key!=null:entry:%p,key:%p\n",entry,entry->key);
    if (hashEqual(entry->key, key)) {
        return true;
    }
//printf("dont find,entry:%p,next:%p\n",entry,entry->next);
    if (entry->next != NULL) {
  //      printf("begin while,entry:%p,next:%p\n",entry,entry->next);
   entry = entry->next; //entry->next出错！
 // while (entry != NULL&&entry->key!=NULL) 
   do{
   // printf("entry:%p,key:%p\n",entry,entry->key);
            if (hashEqual(entry->key, key)) {
                return true;
            }
//printf("get next\n");
            entry = entry->next;

        } while (entry!=NULL&&entry->key != NULL);
//}
//printf("end while\n");    
    return false;
    } else {
        return false;
    }
}

void hashClear(HashMap hashMap)
{
    for (int i = 0; i < hashMap->listSize; i++) {
        // 释放冲突值内存
        Entry entry = hashMap->list[i].next;
        while (entry != NULL) {
            Entry next = entry->next;
            free(entry);
            entry = next;
        }
        hashMap->list[i].next = NULL;
    }
    // 释放存储空间
    free(hashMap->list);
    hashMap->list = NULL;
    hashMap->size = -1;
    hashMap->listSize = 0;
}

HashMap createHashMap()
{
//printf("createhashmap\n");   
 HashMap hashMap = (HashMap)slave_newHashMap();
//printf("after of create hash 1\n");
    hashMap->size = 0;
    hashMap->listSize = 16;
    // hashMap->hashCode = hashCode == NULL ? defaultHashCode : hashCode;
    // hashMap->equal = equal == NULL ? defaultEqual : equal;
    // hashMap->exists = defaultExists;
    // hashMap->get = defaultGet;
    // hashMap->put = defaultPut;
    // hashMap->remove = defaultRemove;
    // hashMap->clear = defaultClear;
    // hashMap->autoAssign = true;
    // 起始分配16个内存空间，溢出时会自动扩充
//printf("after of create hash 2\n");    
hashMap->list = slave_newEntryList(hashMap->listSize);
 //printf("hashmap:%p,hashmap->list:%p\n",hashMap,hashMap->list);   
//Entry p = hashMap->list;
    for (int i = 0; i < hashMap->listSize; i++) {
         hashMap->list[i].key =NULL;
         hashMap->list[i].value =NULL;
         hashMap->list[i].next = NULL;
  //      p[i].key=NULL;
    //    p[i].value=NULL;
      //   p[i].next=NULL;     
// printf("init:key:%p,value:%p,next:%p",hashMap->list[i].key,hashMap->list[i].value,hashMap->list[i].next);    
}

//printf("init:list:%p,next:%p\n",hashMap->list[0],hashMap->list[15].next);
    return hashMap;
}

HashMapIterator createHashMapIterator(HashMap hashMap)
{
    HashMapIterator iterator = slave_newHashMapIterator();
    iterator->hashMap = hashMap;
    iterator->count = 0;
    iterator->hashCode = -1;
    iterator->entry = NULL;
    return iterator;
}

bool hasNextHashMapIterator(HashMapIterator iterator)
{
    return iterator->count < iterator->hashMap->size ? true : false;
}

HashMapIterator nextHashMapIterator(HashMapIterator iterator)
{
    if (hasNextHashMapIterator(iterator)) {
        if (iterator->entry != NULL && iterator->entry->next != NULL) {
            iterator->count++;
            iterator->entry = iterator->entry->next;
            return iterator;
        }
        while (++iterator->hashCode < iterator->hashMap->listSize) {
            Entry entry = &iterator->hashMap->list[iterator->hashCode];
            if (entry->key != NULL) {
                iterator->count++;
                iterator->entry = entry;
                break;
            }
        }
    }
    return iterator;
}

void freeHashMapIterator(HashMapIterator *iterator)
{
    free(*iterator);
    *iterator = NULL;
}
